With the development of mobile communication networks and location search and service technology, such as a GPS, there has recently been a growing interest in an application field that supports location-based service for mobile objects. The location-based service for mobile objects requires k-nearest neighbor queries for efficiently searching for the location information of a mobile object and a static object, such as a gas station.
A database in which the information of road networks, the information of mobile objects, and the information of static objects have been stored is referred to as a road network database. In such a road network database, a road network is modeled by a graph having directionality.
A single road segment corresponds to a main line of a graph, and a point at which two different road segments meet each other corresponds to a node of the graph.
Furthermore, on a road network, facilities, such as a stop, a school and a hotel, are modeled by static objects, and objects having mobility, such as a vehicle and a human, are modeled by mobile objects.
Queries that are used in a road network database include k-nearest neighbor queries, range queries, and spatial join queries.
In the existing Euclidean space, the Euclidean distance between two arbitrary objects can be calculated using only the absolute locations of the objects. However, since a mobile object can move only along a predefined road network in a road network space, the network distance between two objects cannot be calculated using only the absolute locations of the objects. In this case, the network distance between two arbitrary objects refers to the total sum of the lengths of road segments present on the shortest path between the two objects on a road network.
That is, even when absolute locations are the same, the distance varies depending on the status of a network that connects two points. Accordingly, the network distance between two arbitrary points cannot be calculated using only the absolute locations of the two points. Various methods for efficiently obtaining a network distance have been researched. Representative examples thereof include the IER technique, the INE technique, and the VN technique.
The IER technique uses the fact that a Euclidean distance is always shorter than or equal to a network distance. First, candidates are searched for based on a Euclidean distance, and an actual network distance is obtained only for these candidates. Although this technique has an advantage in that storage space overhead is low, query processing performance is also considerably low because many trials and errors are undergone.
Furthermore, the INE technique searches for the presence of a static object while sequentially extending a road segment from a query point. Although this technique has the advantage of low storage space overhead like the IER technique, query processing performance is not sufficient because a plurality of disk accesses is required. The VN technique segments an overall network space into sets of cells based on points at which the distance between each static object and another adjacent static object is equal. For effective query processing, the distances among all static objects, nodes and cell boundary lines within each cell are pre-computed.
The VN technique has excellent query processing performance, but has the disadvantage of excessively high storage space overhead, compared to the IER technique and the INE technique.
Meanwhile, most current location-based services (LBS) for a wireless terminal use a method of determining the single location of a user and providing notification of the location. Furthermore, most multilateral LBS indicate the current location of a corresponding party, and application-type services using the multilateral LBS use a method of text exchange between parties.
In connection with a method of providing notification of the location information of a user in such LBS, the location information of a user, which is the important privacy information of an individual person, must be treated as information that is prohibited from becoming known to other people without the permission of the corresponding person. However, most LBS have a problem in that such a privacy issue is neglected for the sake of user convenience or benefit.
An example of conventional technology related to a method of protecting the location information of a user is disclosed in Korean Patent No. 10-1175719 entitled “Multilateral Location Information Sharing System using Wireless Terminal and GPS.” This conventional technology was devised with the purpose of preventing risk attributable to location tracking, which may be misused for malicious purposes, by means of a system that can clearly identify a receiver and then permit the use of location information via a security authentication mechanism for a counterpart during location information exchange with a third party, thereby limiting and controlling the usage of the location information to the authentication of a counterpart and specific purposes and uses.
According to this preceding technology, the location information of each user is transferred to a counterpart via a GPS under the permission of the user. Accordingly, problems arise in that there is the risk of tracking the information of a user and also the costs of communication between a user and a server increase.
Therefore, there is a rising demand for an LBS protocol that can be easily combined with an algorithm that can effectively limit the range of disclosure of location information, i.e., the private information of a user, and that can also reduce the computational load of an LBS server.